package leetcode.problems.P92反转链表II;

public class ReverseBetween {
}

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

//class Solution {
//    public ListNode reverseBetween(ListNode head, int left, int right) {
//        if (left == right) return head;
//        int nNodes = 0;
//        ListNode prev = new ListNode(-1, head), current = head, next = null;
//        while (current != null) {
//            nNodes++;
//            if (left > 1 && nNodes == left - 1) prev = current;
//            if (nNodes == right) {
//                next = current.next;// next为null，则current为最后一个链表节点
//                break;
//            }
//            current = current.next;
//        }
//        ListNode[] headRear = reverseRecursive(prev.next, current);
//        prev.next = headRear[0];
//        headRear[1].next = next;
//        return left == 1 ? prev.next : head;
//    }
//
//    private ListNode[] reverseRecursive(ListNode left, ListNode right) {
//        if (left == right) {
//
//        }
//        ListNode[] nodes = reverseRecursive(left.next, right);
//        next.next = left;
//    }
//}

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode dummy = new ListNode(-1, head);
        ListNode prev = dummy;
        for (int i = 1; i < left; i++) {
            prev = prev.next;
        }
        // 核心思想：prev不动，不断使 current.next 成为 prev.next
        // prev永远指向left-1位置的节点，current从left开始往后遍历，next指向current+1位置的节点
        // 一次遍历将next位置上的节点放到prev+1位置上，所以迭代终止条件为next指向right位置的节点
        ListNode current = prev.next, next = null;
        for (int i = left; i < right; i++) {
            next = current.next;
            current.next = next.next;
            next.next = prev.next; // 注意此处的prev.next不一定等于current（只在第一次迭代时成立）
            prev.next = next;
        }
        return dummy.next;
    }
}